588D - Duff in Beach - CodeForces Solution

from collections import Counter
mod = 10 ** 9 + 7
n, l, k = list(map(int, input().split()))
if k == 1:
    print(l % mod)
    exit()
a = list(map(int, input().split()))
if l < n:
    a = a[:l]
    n = len(a)
m = {v : i + 1 for i, v in enumerate(sorted(set(a)))}
b = [m[i] for i in a]
g = l // n
r = l % n
k = min(k, g + int(r > 0))
d = Counter(b)
dr = Counter(b[:r])
sd = sorted(d.items())

dp = [0] * (len(m) + 1)
dp[0] = 1
ret = 0
for kk in range(k):
    tmp = [0] * len(dp)
    psum = dp[0]
    for v, c in sd:
        psum = (psum + dp[v]) % mod
        tmp[v] = psum * c % mod
        rep = (g - kk) % mod * c % mod + dr.get(v, 0)
                ret = (ret + psum * rep % mod) % mod
    dp = tmp
print(ret)